Improving-Moves Algorithm (cf. Ex. 1/5)Input: finite strategic game $\game=(N,S,u)$, strategy profile $s \in S$ Output: A PNE $s^\ast \in S$ of $\game$
While $s$ is not a PNE Do
mmchoose $i \in N$ and $s'_i \in S_i$ with $u_i(s'_i,s_{-i}) \gt u_i(s)$
mmset $s \leftarrow (s'_i,s_{-i})$
Return $s$
$L$
$C$
$R$
$T$
$(4,2)$
$(2,3)$
$(3,1)$
$B$
$(2,6)$
$(5,4)$
$(4,6)$
For $\game=(N,S,u)$:
deviation graph $G(\game) \coloneqq (S,E)$ with $e=(s,s') \in E \iff \exists i \in N, s' = (s'_i,s_{-i})$
improvement path $\gamma=(s^0,s^1,\dots)$: path in $G(\game)$ with $u_i(s^{k-1}) \lt u_i(s^k)$ for $i \in N$ with $s^k = (s^k_i,s^{k-1}_{-i})$ f.a. $k$
$\game$ has finite improvement property (FIP) $\coloniff$ every improvement path in $G(\game)$ is finite
§3 Potential Games
For game $\game=(N,S,u)$ and vector $b \in \IRp^N$, a function $P: S \to \IR$ is
exact potential
$\coloniff \forall s \in S, i \in N, s'_i \in S_i: u_i(s'_i,s_{-i}) - u_i(s) = \phantom{b_i\cdot\bigl(}P(s'_i,s_{-i}) - P(s)$
$b$-potential
$\coloniff \forall s \in S, i \in N, s'_i \in S_i: u_i(s'_i,s_{-i}) - u_i(s) = b_i\cdot\bigl(P(s'_i,s_{-i}) - P(s)\bigr)$
ordinal potential
$\coloniff \forall s \in S, i \in N, s'_i \in S_i: u_i(s'_i,s_{-i}) \gt u_i(s) \iff \phantom{\bigl(} P(s'_i,s_{-i}) \gt P(s)$
generalized ordinal potential
$\coloniff \forall s \in S, i \in N, s'_i \in S_i: u_i(s'_i,s_{-i}) \gt u_i(s) \implies \phantom{\bigl(} P(s'_i,s_{-i}) \gt P(s)$
$s \in S$ local maximum of $P$ $\coloniff \forall i \in N, s'_i \in S_i: P(s'_i,s_{-i}) \leq P(s)$
Thm. 3.5: Game $\game$ with ordinal potential $P$. Then
$s \in S$ local maximum of $P \iff s$ PNE of $\game$
$P$ attains its maximum $\implies$ $\game$ has PNE
Thm. 3.6: For finite game $\game$: $\game$ has FIP $\iff$ $\game$ has generalized ordinal potential
Cor. 3.7: Any finite, generalized ordinal game has a PNE.
Cor. 3.11: Exact potentials are unique up to additive constant.
Thm. 3.12: For any game $\game$ the following are equivalent:
$\game$ is an exact potential game
$\forall \gamma$ 4-cycle in $G(\game)$: $\Delta^u(\gamma)=0$
$\forall \gamma,\gamma'$ paths in $G(\game)$ with common start and end: $\Delta^u(\gamma) = \Delta^u(\gamma')$
For $\gamma = (s^0,s^1,\dots,s^K)$ path in $G(\game)$:
\[\Delta^u(\gamma) \coloneqq \sum\nolimits_{k=1}^K\bigl(u_{i_k}(s^k)-u_{i_k}(s^{k-1})\bigr),\]
with $i_k \in N$ s.th. $s^k=(s^k_i,s^{k-1}_{-i})$, is net-improvement along $\gamma$.
Computational Game Theory (WiSe26/27), §3 Potential Games